1. Field of the Invention
This invention relates to improving the performance of matrix evaluations. The invention is also related to an improvement in performance in evaluating sparse matrices having at least one model containing information for at least one node in the matrix being evaluated. The invention is still further related to an improvement in the performance of matrix evaluations where the sparse matrix represents Kirchoff""s voltage and current laws for an electronic circuit being evaluated, and where the models represent specific structures and contain at least one conductance contribution value of an electronic circuit component of the electronic circuit.
2. Discussion of the Background
The use of matrix based solvers (matrix solutions) to simulate transient behavior of electronic circuits dates back to 1975, and is in wide use in the electronic design community. Nagel, L., SPICE 2: A Computer Program to Simulate Semiconductor Circuits, ERL Memo UCB/ERL M75/520, University of California, Berkeley, May 1975, hereinafter, SPICE; see also Cohen, E., Program Reference for SPICE 2, ERL, University of California, Berkeley, June 1976, hereinafter Cohen, and Quarles, T., Analysis of Performance and Convergence Issues for Circuit Simulation, EECS, University of California, Berkeley, April 1989, hereinafter, Quarles. This method of solution relies on the fact that differential circuit equations that describe transient behavior of circuits can be written as conductance coefficients (G) into a matrix, and the matrix can be solved to obtain new voltage values at each node of the circuit.
The use of matrix solutions has relied on a number of techniques to improve solution performance. Starting with SPICE, sparse matrix techniques have been utilized to reduce the amount of memory required to store the entire matrix. While sparse matrix systems reduce the amount of memory needed, they require a trade-off in performance due to the fact that the location of an individual matrix entry must be stored and because the matrix solution cannot be calculated through simple matrix index mathematics as in non-sparse systems.
FIG. 1A is a circuit diagram of a two resistor circuit (R1 and R2) having three circuit nodes (N1, N2, and N3). FIG. 1B is a matrix representing conductance values (G) of the two resistor circuit. The matrix element labeled G1+G2 represents the circuit equation coefficients for the node N2 between the resistors.
In a single processor computer, matrix evaluation cycles proceed according to the flow diagram in FIG. 2. For each time point in the simulation, all of the device models are evaluated and the result is added to the matrix entry in a serial fashion. At Step 20, a model is evaluated. Such model can be, for example, a model representing resistor R1 in FIG. 1A. The model evaluation determines the conductance values (G) of the circuit element, resistor R1. At Step 22, the matrix is loaded with the conductance values determined in the model evaluation Step 20. In this example, the conductance values of the circuit element resistor R, is collectively referred to as a matrix stamp R, is inserted into the matrix (see Matrix stamp of R1, FIG. 1B). Steps 20 and 22 are repeated for each model to be evaluated.
At Step 24, the matrix is solved to determine voltage values at each node of the circuit. At Step 26, a convergence test is utilized to determine whether or not the circuit has reached a steady state solution. An example convergence test compares values at a vector of new nodal voltages (Xi) to values from a last convergent time point (Xixe2x88x921), and is defined as:
Xixe2x88x92Xixe2x88x921xe2x89xa6Abstol+Reltol * Max (Xi, Xixe2x88x921),
where Astol and Reltol are user defined convergence control variables of the simulator (having default values of 1exe2x88x926 and 1exe2x88x923 respectively), and the function Max ( ) returns the largest of two values.
If the convergence test does not reach steady state, the entire process is repeated for another simulated time point. In the above process, because the model evaluation can occupy as much as 50 percent of the processor""s time, this leads to extremely long runs in large circuit simulation can be experienced.
The conventional implementation of matrix solvers has relied on device model structures similar to Resistor Model Structure 30 shown in FIG. 3. Resistor Model Structure 30 stores identifying information 32, including an instance and model identifier, and the conductance value G 36, as evaluated during model evaluation (Step 20 in FIG. 2, for example). In addition, Resistor Model Structure 30 stores the memory locations of the matrix entries (Pointers 38, for example). This mechanism requires that after each device model is evaluated, the new values of G (36, for example) must be xe2x80x98stampedxe2x80x99 into the matrix during the matrix load phase.
In a multiple processor system, each evaluation of a device model can be handed to a separate processor. As shown in FIG. 4, model evaluations 40a, 40b, and 40c are processed in parallel. While this can lead to some improvement in simulation time, the overall performance of the system will not be improved dramatically due to the nature of shared memory systems. Shared memory is utilized because some circuit equations cause overlapping entries at matrix positions where two or more circuit elements meet to form a circuit node, therefore the effect of adding additional processors is reduced because of a time consuming, serial process of matrix load (Step 42).
If each device model is evaluated by a separate processor, then the simulation can enter a situation known as a blocking memory write in which two (or more) processors attempt to write to the same memory location. This can be seen by referring to the matrix entry labeled G1+G2 in FIG. 1B and corresponding to node N2 in FIG. 1A, which shows that the value of this element has conductance contributions G1 and G2 from resistors R1 and R2, respectively.
Some mechanism must be provided to prevent two processors from writing to a given memory location simultaneously. A blocking memory write prevents simultaneous writes by locking a memory location (matrix entry), reading it""s value, adding the evaluation of the other models (conductances) that contribute to this nodal voltage, and then unlocking the memory location. However, blocking memory writes are expensive due to the fact that all other processes that are contributing to the value at the memory location being written are blocked until the lock/unlock cycle completes. Furthermore, in order to avoid an enormous number of memory location lock operations and associated bookkeeping and memory consumption involved in managing those locks, multi-processing systems have historically locked and unlocked the entire matrix before and after each stamping step.
Bischoff and Greenburg""s original method Bischoff, G., and Greenburg, S., Cayennexe2x80x94A Parallel Implementation of the Circuit Simulator SPICE, Digital Equipment Corporation, Hudson Mass., CH2353-1/86/0000/0182 (copyright) 1986 IEEE, hereinafter Bischoff and Greenburg, overcomes this blocking problem by changing the matrix entry from a single scalar value to a sum value and a vector of individual conductances. As shown in FIG. 5, each matrix position (50, for example) includes a vector 52 where each vector entry (G2, for example) is a collection point for a single model evaluation. Thus, if two device models are connected to a circuit node, that node is represented in the matrix as a matrix position having three values, two of which provide locations for non-blocking writes by separate model evaluation processes (vector 52), and one of which is a sum value 54.
The effect of Bischoff and Greenburg""s method on the matrix evaluation loop is shown in FIG. 6. Model evaluations 40a, 40b, and 40c are performed as before, however, matrix loads shown as matrix load 62a, 62b and 62c are now performed in parallel. Each matrix load performs stamping, via nonblocking writes, of individual conductance values from individual circuit elements into a single matrix position (vector entry). Steps 64a, 64b and 64c represent the summing of the sum values at each matrix position (sum value 54, FIG. 5, for example).
Bischoff and Greenburg""s method provides an improvement in evaluation time of circuit simulations. However, because of the complexity of most circuits being evaluated, significant computational time is still required.
Accordingly, it is an object of this invention to provide an improvement in time required to evaluate a matrix by providing an arrangement of device models having values stored therein and providing pointers in the matrix being evaluated to the device model stored values.
It is another object of the present invention to provide an improvement in evaluation of electrical circuits via a matrix having pointers to device models containing conductance values of electronic components in the electrical circuit.
It is yet another object of the present invention to provide a method of evaluating a matrix representing an electrical circuit by eliminating the need for matrix locking and a matrix load phase by reading conductance values for electronic components in the circuit from a device model.
It is yet another object of the present invention to reduce the amount of memory required to maintain a matrix being evaluated.
These and other objects are accomplished by an apparatus for storing and accessing matrix coefficients for a circuit simulation, which apparatus includes an input device configured to input conductance elements corresponding to matrix coefficients, a storage device configured to store each conductance element in at least one component model structure, a data structure comprising plural nodes, each node corresponding to a matrix coefficient and having at least one pointer, a pointer reference mechanism configured to reference pointers in each respective node of the data structure to conductance elements which are stored in the component model structure and which correspond to the matrix coefficient of the respective node, and an access device configured to access one or more of said matrix coefficients utilizing a corresponding node of the data structure.
Alternatively, the above objects may be accomplished via a method of storing and accessing matrix coefficients, comprising the steps of retrieving data elements corresponding to at least one matrix coefficient, storing each data element in at least one model, building a data structure having plural nodes, each node corresponding to a matrix coefficient and having at least one pointer, referencing pointers in each respective node of said data structure to reference model stored data elements corresponding to at least part of the matrix coefficient of the respective node, and accessing a matrix coefficient utilizing a corresponding node of said data structure.
The above described apparatus and method eliminate the matrix load phase in favor of directly reading the conductance values from the model data structures. This leads to performance enhancement by eliminating the need to lock the matrix for writes. It also reduces the amount of memory required by reducing the number of double floating point values held in the matrix (total of 32 bytes for a resistor) to four single precision pointers (16 bytes total).
Other aspects and advantages of the present invention can be seen upon review of the figures, the detailed description, and the claims which follow.